import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;
import java.util.Vector;

import soot.SootMethod;
import soot.Unit;
import soot.jimple.toolkits.callgraph.CallGraph;
import soot.jimple.toolkits.callgraph.Targets;

public class PathContainer {
	/***
	 * the symbol of start
	 */
	String start;
	/***
	 * the symbol of end
	 */
	String end;
	/**
	 * write to the specific file
	 */
	OutputStream f0;

	/**
	 * call graph
	 */
	CallGraph cg;
	/**
	 * start method to extend
	 */
	IndexMethod currentMethod;
	/**
	 * record how many paths have been written
	 */
	int count;

	public PathContainer(String start, String end, IndexMethod startMethod,
			CallGraph cg) {
		try {
			f0 = new FileOutputStream(DirectoryUtil.OUTPUT_PATH);
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
		this.start = start;
		this.end = end;
		this.currentMethod = startMethod;
		this.cg = cg;
		this.count = 0;
	}

	/**
	 * the main part to interator the project and find the path between start
	 * point and end point
	 * 
	 */
	public void process() {
		Stack<StaticPath> otherPaths = new Stack<StaticPath>();
		// whether finds the end point, if so ,break and record the path
		boolean findEnd = false;
		// initial the first few paths of the method where the start point
		// belongs
		for (int i = 0; i < currentMethod.size(); i++) {
			IndexPath path = currentMethod.getPath(i);
			if (path.contains(start)) {
				otherPaths.add(transferIndexToNormal(path));
			}
		}
		while (!otherPaths.empty()) {
			findEnd = false;
			StaticPath path = otherPaths.pop();
			for (int i = path.getCursor(); i < path.size(); i++) {
				// iterator all the nodes of the current path
				IndexNode node = path.getNode(i);
				path.recordNode(i);
				if (node.getValue().equals(end)) {
					findEnd = true;
					break;
				}
				if (!node.isLeaf()) {
					if (node.getMethod() == null) {
						findMethodFromNode(node);
					}
					if (!path.isCalled(node.getMethod().getName())) {
						path.addCalled(node.getMethod().getName());
						addExtendPaths(path, i + 1, node.getMethod(),
								otherPaths);
					}
				}
				// move the cursor on
				path.next();
				if (path.getCursor() == path.size()) {
					findEnd = false;
					break;
				}
			}
			// only write the path which contains the end point
			if (findEnd) {
				try {
					f0.write(path.getCurrentTrace().getBytes());
					count++;
					if (count % 50000 == 0) {
						System.out.println(count + " paths found "
								+ otherPaths.size() + " to be done");
					}
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}
		try {
			f0.close();
			System.out.println(count + " paths found");
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	/**
	 * insert the sub-paths at the specific position of the current path
	 * 
	 * @param path
	 *            the current path
	 * @param j
	 *            the position
	 * @param method
	 *            the subpaths belongs to this method
	 * @param otherPaths
	 *            the stack storing other paths to be done
	 */
	private void addExtendPaths(StaticPath path, int j, IndexMethod method,
			Stack<StaticPath> otherPaths) {
		path.insertPath(method.getPath(0), j);
		for (int i = 1; i < method.size(); i++) {
			IndexPath ipath = method.getPath(i);
			StaticPath spath = path.clone();
			spath.insertPath(ipath, j);
			otherPaths.add(spath);
		}
	}

	/**
	 * we need to tranform an index path to a static Path which we can use for
	 * experiments. the static path shall start with the start point
	 * 
	 * @param path
	 *            the index path
	 * @return the static form of the path
	 */
	private StaticPath transferIndexToNormal(IndexPath path) {
		StaticPath spath = new StaticPath();
		for (int i = path.IndexOf(start); i < path.size(); i++) {
			spath.add(path.getNode(i));
			if (path.getNode(i).getValue().equals(end)) {
				break;
			}
		}
		spath.setCursor(0);
		return spath;
	}

	/**
	 * after building the indexs, the call point is not associated with the
	 * method it calls, this method can help to associate the call point with
	 * the method it calls
	 * 
	 * @param node
	 *            the call point
	 */
	private void findMethodFromNode(IndexNode node) {
		Iterator targets = new Targets(cg.edgesOutOf(node.getUnit()));
		while (targets.hasNext()) {
			SootMethod sMethod = (SootMethod) targets.next();
			String sName = sMethod.toString();
			IndexMethod imethod = IndexContainer.getMethod(sName);
			if (imethod == null || sName.equals("<clinit>")
					|| sName.equals("<init>")) {
				continue;
			}
			node.setMethod(imethod);
		}
	}
}
